1. Field of the Invention
The present invention is related to the analysis of the concurrently processed computationally complex algorithm and, more particularly, to a data processing system that uses a Petri net model of concurrently processed computationally complex algorithms.
2. Description of the Related Art
One method which is currently being developed to increase the execution speed of computers is parallel processing of primitive operations in an algorithm. The hardware used in a data processing system having such a parallel architecture is relatively easy to develop by using, e.g., identical, special purpose computing elements each of which can access a shared memory. In comparison, it has been much more difficult to develop the software required to schedule, coordinate and communicate between the individual computing elements and other portions of the data processing system, such as external data input/output to and from terminals, printers, tape drives, etc.
Conventional multiprocessing systems typically execute a program in a single processor, while different program(s) executes in the other processor(s). The scheduling, coordination and communication problems in such multiprocessor systems are among the most complex addressed by existing computer systems. However, in the type of parallel processing discussed above, solution of coordination and communication problems is even more critical, because a single program or algorithm is being processed by more than one computing element. As a result, in addition to sharing the hardware, as in the conventional multiprocessor system, the computing elements also share data. Since a first instruction or task may be performed in a first computing element to generate intermediate data used in a second task performed by a second computing element, the flow of data in the system must be carefully controlled. Such data processing systems which referred to as performing concurrent parallel processing and may have a data-driven architecture, i.e., controlled by data flow, or a demand-driven architecture.
The differences between a data processing system performing concurrent operations and a system organized according to von Neumann principles render conventional methods of describing and defining computer operation inadequate. For example, flowcharts or conventional algorithm graphs which are useful in describing the operation of a von Neumann structure are insufficiently descriptive of the operation of a concurrent processing system. Techniques for defining and controlling the operation of a concurrent processing system is critical for the development of software to be executed on data processing systems having, e.g., a data-driven architecture.
Efforts have been made to define tasks to be performed in a data processing system for concurrent execution of primitive operations of an algorithm. For example, previous proposals for assignment of the computing elements or functional units to particular tasks have used either static or dynamic assignment. When static assignment is used, the tasks performed by each functional unit is determined during the design of a program. This requires a great deal of specificity in the program, increasing the amount of time required for development and thereby reducing the benefits gained from using data flow control in a processing system. Dynamic assignment, on the other hand, determines the task performed by each functional unit at the beginning of execution of an algorithm. This reduces the effort required during programming, but still results in fixed correspondence between a functional unit and a primitive operation during the processing of the algorithm.